This invention relates to a control system for fetching an instruction group following a branch target instruction when a branch instruction is executed in a computer system using a one-cycle pipeline system and more particularly, to an instruction fetching control system for performing a prior branch judgement by judging whether a condition judgement can be performed in a cycle preceding a branch judgement cycle in which the branch instruction is executed.
FIG. 1 shows a view for explaining an execution of a branch instruction in a prior-art one-cycle pipeline system. The numbers (1) to (12) at the top of the drawing represent respective timings of machine cycles and process part symbols D, A, T, B, E, and W of respective instructions represent respective processing states (which are also called xe2x80x9ccyclesxe2x80x9d or stages hereinafter) in the pipeline control.
D indicates a decoding cycle for decoding an instruction to be executed. A is an address calculating cycle for performing an address calculation to fetch the branch target instruction, T is an address translating cycle for translating a logical address into a real address, B is a cycle for fetching a branch target instruction, E is a branch judging cycle for performing a judgement as to whether the branch condition is successful or not and W is a cycle for storing an arithmetic operation result. These cycles are well known.
In the pipeline system, an instruction to be executed is prefetched. The prefetch of the executed instruction is also conducted in a pipeline manner. The periods for period part symbols IA, IT and IB in the instruction prefetch pipeline in the lower part of FIG. 1 represent process cycles for prefetching an instruction following the branch instruction and IA*, IT* and IB* represent process cycles for prefetching the instruction following the branch target instruction. For example, address calculating cycle IA, address translating cycle IT and cycle IB for fetching data from a buffer in the instruction prefetch pipeline shown in process IPP, is for fetching fetching instruction {circle around (N)}+3 where the branch of branch instruction B is not successful.
In FIG. 1, symbols xe2x80x9cNextxe2x80x9d, shown in the lower part of FIG. 1, represent the kind of the instruction to be prefetched. These symbols show that the instruction (also called xe2x80x9cNext sidexe2x80x9d of the part) following the branch instruction is prefetched. xe2x80x9cTargetxe2x80x9d indicates that an instruction (called xe2x80x9cTarget sidexe2x80x9d of the part) following the branch target instruction is prefetched and xe2x80x9c(Next)xe2x80x9d shows the case in which the instruction following the branch instruction is prefetched and the case in which the instruction is not fetched are selected.
Branch instruction {circle around (B)} is first executed in the example shown in FIG. 1 and instruction sets {circle around (N)}, {circle around (N)}+1, {circle around (N)}+2 and {circle around (N)}+3 following the branch instruction {circle around (B)} are then executed sequentially. The branch condition is successful in the branch judging cycle (E state) of branch instruction {circle around (B)} in timing step (5) and branch target instruction {circle around (T)} and instruction sets {circle around (T)} {circle around (T)}+1, {circle around (T)}+2, . . . following the branch target instruction are executed. FIG. 1 shows the case where the number of branch target instructions {circle around (T)}, {circle around (T)}+1, {circle around (T)}+2 obtained by one time fetch of the branch instruction carried out during B state of branch instruction {circle around (B)} is three and the branch is carried out depending on the result of the branch judgement during E state of branch instruction {circle around (B)} and the execution of branch target instructions {circle around (T)}, {circle around (T)}+1, {circle around (T)}+2 is started smoothly.
In a pipeline system, as recited above, an instruction prefetch is processed as a pipeline. Thus, it is necessary to determine the fetch address at which an address calculation IA should be conducted in a stage which is two cycle prior to stage IB in which a prefetch of an instruction is actually carried out, as shown in FIG. 2. FIG. 2 shows a view for explaining an instruction prefetch pipeline. Period part symbols IA, IT, IB show respective process stages. IA designates an address calculation cycle (ADRS), IT represents an address translation cycle (TLB/TAG) and IB represents an instruction fetching cycle (FETCH).
Generally, i.e., without being limited to a branch instruction, it is necessary to determine the addresses of instructions xe2x80x9cNext 1xe2x80x9d and xe2x80x9cNext 2xe2x80x9d to be prefetched in the IA cycle two cycles prior to the IB cycle in which an instruction is actually fetched.
Where the pipeline process is carried out as shown in FIG. 1 and an instruction prefetch is executed in the form shown in FIG. 2, then, there is the problem that an instruction prefetch, which should be carried out in the same cycle at timing (5) in FIG. 1 as branch judging cycle (E state) of branch instruction {circle around (B)} in FIG. 1 or in the next cycle (timing (6) and (7) in FIG. 1), is conducted as to a part (xe2x80x9ctarget sidexe2x80x9d) following branch target instruction {circle around (T)} or a part (xe2x80x9cnext sidexe2x80x9d) following branch instruction {circle around (B)}.
As shown in FIG. 3, in the example (No. 1) where a target side instruction fetch does not exist when the branch target instruction starts, the branch condition of branch judging cycle (E state) of branch instruction {circle around (B)} is successful and only T of one machine instruction of the branch target occurring during B state (timing (4) in FIG. 3) is fetched, branch target instruction {circle around (T)} can then be executed during timing (5) but, at this time instruction {circle around (T)}+1 of Target Side is not yet fetched, and thus, execution of instruction {circle around (T)}+1 cannot start during timing (6).
In order to solve this problem, the means for fetching the branch target instruction {circle around (T)} together with instructions {circle around (T)}+1, {circle around (T)}+2 . . . , following the branch target instruction in B state of branch instruction {circle around (B)} is considered. In this case, the amount of instruction which can be fetched by one fetch operation, is about 1 to 2 instruction lengths, although the amount of instruction depends on the method of forming a central processor unit (CPU) and an instruction length. As shown in the example (No. 2) where the target side instruction is not fetched upon a start of the branch target instruction shown in FIG. 4 and where two instructions comprising branch target instruction {circle around (T)} and {circle around (T)}+1 are fetched, instruction {circle around (T)}+2 of the target side is not fetched at timings (5) and (6). Therefore, instruction {circle around (T)}+1 cannot be executed in timing (7) and the central processor unit (CPU) falls into a state of waiting for an instruction to be executed to be fetched.
In order to solve the problem, as shown in FIG. 4, for example, it is necessary to determine the fetch address, at least upon the timing (4) when an instruction {circle around (T)}+2 of a target side is fetched in timing (6). The determination of the fetch address uses a result of an address calculation at an A state of branch instruction {circle around (B)}. Thus, it is not necessary to wait for an E cycle to determine whether the branch condition is successful or not. However, when the target side instruction fetch is driven, it is necessary thereafter to add an extra hardware to switch the process to an instruction fetch of a part following the branch instruction.
Namely, when the branch target instruction address is maintained and the instruction fetch following the branch target instruction is conducted, the means for updating this instruction fetch, namely, the means for calculating an address of an instruction following the branch target instruction, is necessitated independently of the address calculating means of the instruction following the branch instruction of the next side.
An object of the present invention is to provide an instruction fetching control system for effectively prefetching an instruction set following the branch target instruction, where the branch instruction is a non-condition branch instruction or an instruction in which the branch can be predicted.
A condition branch instruction for judging the value of the flag set (or condition code) which is updated in accordance with an execution of the operation instruction, represents the branch instruction.
Where an operation instruction is provided immediately before the condition branch instruction and the flag sets is updated in E state of the operation instruction, the branch judgement cannot be carried out at least until the E state of the branch instruction is executed. This is because the updating of the flag sets in the operation instruction is usually executed after an operation cycle.
However, where an operation instruction is not executed immediately before it, the judgement can be carried out without waiting for the original judgement cycle (i.e. E cycle) of the branch instruction.
On the other hand, some branch instructions are branched without any conditions and the resulting non-condition branches are determined based on an instruction code of the branch instruction. For example, in commercially available systems, BAL (branch and link) instructions and BAS (branch and safe) instructions are non-condition instructions and they can be judged based on the instruction code. The BC (branch condition) instruction is a condition branch instruction, but where bits 8 to 11 of the instruction code are Xxe2x80x2Fxe2x80x2 (hexa decimal number) and bits 12 to 15 are not Xxe2x80x2Oxe2x80x2, the process performs non-condition branch. Where bits 8 to 11 or bits 12 to 15 are Xxe2x80x2Oxe2x80x2, the process is not branched.
In this case, the process is branched without any condition, whether or not the branch condition is successful or unsuccessful. Thus, a control can be effectively moved to fetch an instruction set following the branch instruction.
This is conducted to drive a head address in which instruction {circle around (1)} of buffer memory 15 is stored.
The present invention provides an instruction fetching control system for executing and prefetching an instruction and for prefetching the branch target instruction of the branch instruction prior to the branch judgement cycle. The system comprises means for performing a prior branch judgement based on an instruction code within the branch instruction prior to the branch judgement cycle of the pipeline when the above instruction is executed, means for detecting whether the condition judgement can be carried out in the preceding cycle and for performing the branch judgement, and means for starting a prefetch of instruction sets following the above branch target instruction without waiting for the branch judgement cycle in the pipeline of the branch instruction when the branch judgement means determines that the branch is successful.
When the branch instruction is executed, it is judged whether the branch judgement can be carried out in the cycle preceding the branch condition judgement cycle of the pipeline. This is done in order to perform an instruction prefetching when the branch instruction is executed, thereby performing the branch judgement. If the branch is successful, the instruction of a part following the branch target instruction upon the next cycle of the decode start of the branch target instruction is fetched to the instruction register and the instruction decode is carried out in a pipeline manner. Thus, the central processor unit (CPU) is prevented from falling into a state in which it must wait for an instruciton fetch.